In recent years, communication technology has widely spread in terms of number of users and amount of use of the telecommunication services by the users. This also led to an enormous increase in the information and data amounts exchanged via the existing communication systems.
Thereby, for the users of communication systems there has arisen a remarkable problem of handling the huge information amounts they receive, in particular with respect to the handling of unsolicited or undesired information. Such spamming information (spamming: the use of any electronic communication medium to indiscriminately send unsolicited messages in bulk) may easily exceed the amount of desired “real” information by far. Such a situation not only makes it at least annoying and/or difficult for the users to filter out their desired “real” information but also easily leads to an overload of the capacity of information systems, such as for example the storage space of personal mailboxes.
Currently, the problem outlined above is prevalent in the Internet and especially in ad-hoc and/or sensor networks. However, it is not restricted to these kinds of networks but is particularly relevant to any communication system in which unknown (possibly unregistered) communication parties are present. From today's perception, this is notably the case in communication systems without a central party taking care of, for example, a centralized network and/or user management, security functions, or the like. As an example for such a system a distributed system environment such as in a peer-to-peer (P2P) system can be mentioned. Existing instances of this problem include:                e-mail, wherein an open e-mail infrastructure requires that anybody is able to send e-mail to anybody without prior mutual introduction;        WWW (world wide web) sites with persistent identities for their users that are managed by the WWW site itself; and        network services provided by heavily resource constrained devices e.g. over wireless proximity networks, such as for example mobile devices.        
For many of these scenarios or settings a unifying characteristic is that ‘identities’ of users can be generated at will (because of not being controlled by a central party) and are not managed by any central party.
When performed by a malicious party, such a situation of one party, e.g. a user (or user equipment) or network element, falsely claiming multiple identities has been called the “Sybil Attack” in literature. The “Sybil Attack” can thus be regarded as a kind of malicious identity fabrication and consequently undermines an assumed mapping between identity and entity in that the malicious party presents multiple (fabricated) identities to other parties.
The “Sybil Attack” has been discussed extensively in literature and was originally introduced in “The Sybil Attack” by John R. Douceur, Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS02), Cambridge, Mass. (USA), March 2002.
A problem posed by the Sybil attack is compounded by the danger that a malicious party can gain control of a considerable and possibly even huge amount of networked computers on e.g. the Internet via worms, trojans and other malware. That is, a substantial fraction of the system can be controlled by the malicious party, thereby for example undermining the redundancy in the system which is actually indented to resist security threats. As such, already existing legitimate authorizations and identities can be compromised and placed under the control of a malicious party.
Such problems are underpinnings of the spam (i.e. unsolicited mass e-mailing) problem currently existing on the Internet.
A solution according to known prior art, for example being proposed in the above-mentioned paper of Douceur, is the insertion of a trusted third party into the system, which is arranged to certify identities. However, such a trusted third party would pose additional costs and efforts (concerning e.g. management or implementation) to the communication system.
Another approach to overcome or at least mitigate the above problems is referred to by the keyword “proof-of-work”. Generally speaking, a proof-of-work system is a system used to prove that a device, such as a communication party, has done some “work”, usually meaning it has spent some processing time and/or capacity. Thus, as concerns for example the prevention of spam, any computer that wants to send an e-mail has to produce such a proof-of-work before the receiver accepts the e-mail from this computer. The idea is that a party has to prove to be honest or “good-natured” by performing rather useless work, thereby hampering abuse or malpractice.
There exist some prior art in terms of proofs-of-work.
For example, the “penny black” project at Microsoft research presents papers related to proofs-of-work at http://research.microsoft.com/research/sv/PennyBlack.
The idea of proofs-of-work has been presented in the paper “Pricing via Processing or Combatting Junk Mail” by C. Dwork and M. Naor, Lecture Notes in Computer Science, 1993, pp. 137-147 (Proceedings of CRYPTO'92). Therein, also proofs-of-work based on signature schemes are used. In this paper the schemes however do not limit the applicability of the proof-of-work and also reveal it. Hence, they are not suitable for solving the above problem, i.e. for example for introducing new identities to each other.
Interactive proofs-of-work were introduced via the concept of client puzzles, originally designed to fight session object depletion attacks. These have been introduced in the paper “Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks” by A. Juels and J. Brainard, in S. Kent, editor, Proceedings of NDSS '99 (Networks and Distributed Security Systems), pages 151-165, 1999. These protocols can limit the applicability of the proof-of-work, but are interactive, and hence not applicable in e.g. store-and-forward networks. Additionally, it is not proposed or even suggested how such protocols could be used for solving the above problem, i.e. to introduce new identities to each other.
The idea of using proofs-of-work to do something “useful” instead of just wasting computational power has been introduced via the concept of “bread pudding protocols”. This has been introduced in “Proofs of work and bread pudding protocols” by M. Jakobsson and A. Juels, in Proceedings of the IFIP TC6 and TC11 Joint Working Conference on Communications and Multimedia Security (CMS'99), Leuven, Belgium, September 1999.
None of the mentioned prior art approaches however provides for a solution suitable for the scenarios described above, in particular in connection with a Sybil Attack. Thus, the known prior art is not suited to solve the problems underlying the present invention in a practically acceptable manner.
Thus, a solution to the above problems and drawbacks is still needed for providing an improved introduction of two mutually unknown communication parties to each other in the absence of a trusted third party.